package leecode.q1293;

import java.util.ArrayList;
import java.util.List;

class Solution {
    int k;

    int minSize;

    int m;

    int n;

    public int shortestPath(int[][] grid, int k) {
        this.k = k;
        m = grid.length - 1;
        n = grid[0].length - 1;

        if (m == 0 && n == 0) {
            return 0;
        }
        minSize = grid.length + grid[0].length - 1;

        // 1、找出所有路径
        // 2、计算1的个数
        // 3、大于k，还没到终点，立马截止
        findAllPath(0, 0, 0, grid, new ArrayList<>());
        return minSize == (grid.length * grid[0].length + 1) ? -1 : minSize - 1;
    }

    private void findAllPath(int x, int y, int sumOne, int[][] grid, List<String> curPath) {
        if (curPath.size() >= minSize && minSize != -1) {
            return;
        }
        if (x < 0 || x > m || y < 0 || y > n) {
            return;
        }
        if (curPath.contains(x + " " + y)) {
            return;
        }
        if (grid[x][y] == 1) {
            sumOne++;
        }
        if (sumOne == k + 1 && (x != m || y != n)) {
            System.out.println(x + "--超出--" + y);
            return;
        }

        if (sumOne <= k && x == m && y == n) {
            curPath.add(x + " " + y);
            if (curPath.size() < minSize) {
                minSize = curPath.size();
            }
            System.out.println("sumOne = " + sumOne + ",curPath = " + curPath);
            curPath.remove(curPath.size() - 1);
            return;
        }
        curPath.add(x + " " + y);
        findAllPath(x + 1, y, sumOne, grid, curPath);
        findAllPath(x, y + 1, sumOne, grid, curPath);
        findAllPath(x - 1, y, sumOne, grid, curPath);
        findAllPath(x, y - 1, sumOne, grid, curPath);
        curPath.remove(curPath.size() - 1);
    }
}
